package com.code.test.second.link;

/**
 * 19.删除链表的倒数第N个节点
 * 力扣题目链接
 * <p>
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 进阶：你能尝试使用一趟扫描实现吗？
 */
public class SCode19 {
    public static void main(String[] args) {
        SNode head = new SNode(1);
        SNode second = new SNode(2);
        SNode third = new SNode(3);
        SNode n4 = new SNode(4);
        SNode n5 = new SNode(5);
        SNode n6 = new SNode(6);
        SNode n7 = new SNode(7);

        head.setNext(second);
        second.setNext(third);
        third.setNext(n4);
        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);

        SNode node = removeNode(head, 2);
        int a = 2;

    }

    /**
     * 双指针法
     */
    public static SNode removeNode(SNode root, int n) {
        SNode cur = root;
        /**
         * 快指针先走n步,
         * 然后快慢指针再同时走到最后
         * 这里的作用是让2个拉开n个差距，走到最后是因为求的是倒数
         */
        SNode dummy = new SNode(-1);
        dummy.next = root;
        SNode fast = dummy;
        SNode slow = dummy;
        /**
         * TODO 注意，这里是<=n
         * =n，是要让fast多往后移动一个节点
         * 这样slow在追赶的时候也是少一个节点，能够指到要删除节点的前一个
         * 否则会=要删除的节点
         */
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        //两个一起向后走到最后，中间会差了n,
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        if (slow.next != null) {
            slow.next = slow.next.next;
        }

        return dummy.next;
    }
}
